import java.util.ArrayList;

// 定义大顶堆类，使用 Integer 类型
public class MaxHeap {
    // 使用 ArrayList 存储堆中的元素
    private ArrayList<Integer> data;

    // 构造方法，指定初始容量
    public MaxHeap(int capacity) {
        data = new ArrayList<>(capacity);
    }

    // 无参构造方法
    public MaxHeap() {
        data = new ArrayList<>();
    }

    // 判断堆是否为空
    public boolean isEmpty() {
        return data.isEmpty();
    }

    // 获取堆的大小
    public int size() {
        return data.size();
    }

    // 返回指定索引位置元素的父节点索引
    private int parent(int idx) {
        if (idx == 0) {
            throw new IllegalArgumentException("index-0 doesn't have parent");
        }
        return (idx - 1) / 2;
    }

    // 返回指定索引位置元素的左孩子节点索引
    private int leftChild(int idx) {
        return 2 * idx + 1;
    }

    // 返回指定索引位置元素的右孩子节点索引
    private int rightChild(int idx) {
        return 2 * idx + 2;
    }

    // 向堆中添加元素
    public void add(Integer e) {
        data.add(e);
        siftUp(data.size() - 1);
    }

    // 上浮操作，使新加入的元素调整到合适位置以维持大顶堆性质
    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)) < data.get(k)) {
            swap(k, parent(k));
            k = parent(k);
        }
    }

    // 交换 ArrayList 中两个索引位置的元素
    private void swap(int i, int j) {
        Integer temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    // 获取堆中的最大元素（堆顶元素）
    public Integer findMax() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Can not findMax when heap is empty");
        }
        return data.get(0);
    }

    // 取出堆顶元素（最大元素）
    public Integer extractMax() {
        Integer ret = findMax();
        swap(0, data.size() - 1);
        data.remove(data.size() - 1);
        siftDown(0);
        return ret;
    }

    // 下沉操作，使堆顶元素调整到合适位置以维持大顶堆性质
    private void siftDown(int k) {
        while (leftChild(k) < data.size()) {
            int j = leftChild(k);
            if (j + 1 < data.size() && data.get(j + 1) > data.get(j)) {
                j = rightChild(k);
            }
            if (data.get(k) >= data.get(j)) {
                break;
            }
            swap(k, j);
            k = j;
        }
    }

    // 取出堆顶元素，并加入一个新元素
    public Integer replace(Integer e) {
        Integer ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }
}
